package com.techyuan.algorithm.questions;

import com.techyuan.algorithm.utils.PrintUtil;

import java.util.Arrays;

/**
 * 最大子数组-分治算法
 *
 * @author derek.tian on 2016/11/23.
 */
public class FindMaxinumSubarrayByDA {
    public static void main(String[] args) {
        Integer[] quesList = createQuesList();
        PrintUtil.printArrPretty(quesList, "原始数组:%s");
        MaxinumResult questResult = findMaxinumSubarray(quesList, 0, quesList.length - 1);
        PrintUtil.printArrPretty(Arrays.copyOfRange(quesList, questResult.getLow(), questResult.getHight() + 1), "最大子数组为:%s,子数组和为:" + questResult.getSum());
    }

    /**
     * 查找最大子数组
     *
     * @param qArr
     * @param low
     * @param high
     * @return
     */
    private static MaxinumResult findMaxinumSubarray(Integer[] qArr, int low, int high) {
        if (low == high)
            return new MaxinumResult(low, high, qArr[low]);
        else {
            int mid = (int) Math.floor((low + high) / 2);
            MaxinumResult leftResult = findMaxinumSubarray(qArr, low, mid);
            MaxinumResult righResult = findMaxinumSubarray(qArr, mid + 1, high);
            MaxinumResult crossResult = findCrossMaxinumSubarray(qArr, low, mid, high);
            if (leftResult.getSum() >= righResult.getSum() && leftResult.getSum() >= crossResult.getSum())
                return leftResult;
            else if (righResult.getSum() >= leftResult.getSum() && righResult.getSum() >= crossResult.getSum())
                return righResult;
            else
                return crossResult;
        }
    }

    private static MaxinumResult findCrossMaxinumSubarray(Integer[] qArr, int low, int mid, int high) {
        MaxinumResult crossResult = new MaxinumResult();
        long leftSum = Long.MIN_VALUE;
        long sum = 0;
        for (int i = mid; i >= low; i--) {
            sum = sum + qArr[i];
            if (sum > leftSum) {
                leftSum = sum;
                crossResult.setLow(i);
            }
        }

        long rightSum = Long.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= high; i++) {
            sum = sum + qArr[i];
            if (sum > rightSum) {
                rightSum = sum;
                crossResult.setHight(i);
            }
        }
        crossResult.setSum(leftSum + rightSum);
        return crossResult;
    }

    /**
     * 创建问题数组
     *
     * @return
     */
    private static Integer[] createQuesList() {
        return new Integer[]{2, 4, -7, 5, 2, -1, 2, -4, 3};
    }

    private static class MaxinumResult {
        public MaxinumResult() {
        }

        public MaxinumResult(int l, int h, long sum) {
            this.low = l;
            this.hight = h;
            this.sum = sum;
        }

        private int low;
        private int hight;
        private long sum;

        public void setLow(int low) {
            this.low = low;
        }

        public int getLow() {
            return low;
        }

        public void setHight(int hight) {
            this.hight = hight;
        }

        public int getHight() {
            return hight;
        }

        public long getSum() {
            return sum;
        }

        public void setSum(long sum) {
            this.sum = sum;
        }
    }
}
